Linear Recurrence

定义 Definition

linear recurrence（线性递推/线性递推关系）：一种用前面若干项的线性组合来定义数列后续项的关系式。常见形式为
(a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k})（系数 (c_i) 为常数）。
（在更广义用法中，也可包含带常数项的“非齐次”线性递推。）

发音 Pronunciation (IPA)

/ˈlɪniər rɪˈkʌrəns/

例句 Examples

A Fibonacci sequence is defined by a linear recurrence.
斐波那契数列由一个线性递推关系定义。

To analyze the algorithm, we solved the linear recurrence and obtained a closed-form bound.
为了分析该算法，我们求解了这个线性递推，并得到了一个封闭形式的界。

词源 Etymology

linear 来自拉丁语 linea（“线、绳、线条”），在数学中引申为“满足线性（一次）关系、可用加法与数乘组合”的含义；recurrence 来自拉丁语 recurrere（“跑回、再次出现”），表示“反复出现/递推”。合在一起，linear recurrence 指“以线性方式反复生成下一项的递推关系”。

相关词 Related Words

• Characteristic Equation
• Closed Form
• Difference Equation
• Fibonacci
• Generating Function
• Homogeneous
• Nonhomogeneous
• Recursion
• Sequence

文学与经典著作 Literary Works

• Concrete Mathematics（Graham, Knuth, Patashnik）中大量讨论用线性递推分析与求解计数问题。
• Generatingfunctionology（Herbert S. Wilf）用生成函数系统处理包括线性递推在内的数列问题。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）在算法分析章节中使用并求解线性递推（如分治递推）。